package com.huhu.sort;

import java.util.Random;

public class QuickSort {

    /**
     * 排序
     * @param arr
     * @param l
     * @param r
     */
    public static void quicksort(int arr[],int l,int r){
        if(l<r) {
            Random rand = new Random();
            int i, j, x;
            i = l;
            j = r;
            int random = rand.nextInt(j - i + 1) + i;
            swap(arr[i],arr[random]);
            x = arr[i];
            while (i < j) {
                //为什么还要判断i<j呢？
                //防止while判断越界
                while (i < j && arr[j] > x) {
                    j--;//从右往左寻找大于x的值
                }
                if (i < j) {
                    //将这个小于x的值赋值给arr[i],i++
                    arr[i++] = arr[j];
                }
                while (i < j && arr[i] < x) {
                    i++;//从左从有寻找小于x的值
                }
                if (i < j) {
                    //将这个大于x的值赋值给arr[j],j--
                    arr[j--] = arr[i];
                }
            }
            //将x放到合适的位置
            arr[i] = x;

            //开始递归
            quicksort(arr, l, i - 1);
            quicksort(arr, i + 1, r);
        }
        else{
            return;
        }
    }

    /**
     * 三路快排
     * @param arr
     * @param l
     * @param r
     */
    public static void quick3sort(int arr[],int l,int r){
        if(l<r){
            //lt记录小于x的值的位置
            //rt纪录大于x的值
            //i记录排序的地点
            int lt,rt,i,x;
            lt=l;
            rt=r;
            i=l+1;
            x=arr[lt];
            while(lt<rt){
                if(arr[i]<x){
                    swap(arr[i],arr[lt+1]);
                    i++;
                    lt++;
                }
                else if(arr[i]>x){
                    swap(arr[i],arr[rt]);
                    rt--;
                }
                else{
                    i++;
                }
            }
            swap(arr[lt],x);
            //开始递归
            quicksort(arr, l, lt-1);
            quicksort(arr, rt, r);
        }
    }

    /**
     * 交换
     * @param i
     * @param j
     */
    public static void swap(int i,int j){
        int m;
        m=i;
        i=j;
        j=m;
    }

    /**
     * 主函数
     * @param args
     */
    public static void main(String[] args) {
        int i;
        int a[] = {30,40,60,10,20,50,20,30};

        System.out.printf("before sort:");
        for (i=0; i<a.length; i++) {
            System.out.printf("%d ", a[i]);
        }
        System.out.printf("\n");

        quicksort(a, 0, a.length-1);

        System.out.printf("after  sort:");
        for (i=0; i<a.length; i++) {
            System.out.printf("%d ", a[i]);
        }
        System.out.printf("\n");

        quick3sort(a, 0, a.length-1);

        System.out.printf("after  sort:");
        for (i=0; i<a.length; i++) {
            System.out.printf("%d ", a[i]);
        }
        System.out.printf("\n");
    }


}
